• CPU Scheduling
• Page Replacement in OS
• Disk Scheduling

Operating System

Disk Scheduling

Disk Scheduling in Operating System

Disk scheduling is the process used by an operating system to decide the order in which pending disk I/O requests should be serviced. When several processes request data from different locations on a hard disk, the OS must decide which request to serve first. The main goal is to reduce disk access time and improve performance.

For disk scheduling, the basic calculation is:
Head Movement=|Current Position-Next Request|

The smaller the total head movement, generally the better the disk scheduling performance.

Total head movement is the sum of all individual movements.

Why is Disk Scheduling Needed?

A traditional hard disk has a read/write head that moves across tracks to access data. Moving the head takes time, called seek time. For example, suppose the current head position is 50 and requests are:

82, 170, 43, 140, 24, 16, 190

If the OS processes these requests in a poor order, the head may travel a very long distance. Disk scheduling algorithms try to determine a better order.

Common Disk Scheduling Algorithms

Algorithm	Basic Idea
FCFS	Services requests in the order they arrive
SSTF	Services the request closest to the current head position
SCAN	Head moves in one direction, servicing requests, then reverses
C-SCAN	Services requests in one direction only, then jumps back
LOOK	Similar to SCAN, but reverses at the last request instead of the disk end
C-LOOK	Similar to C-SCAN, but jumps from the last request to the first request

Important Performance Measures
Disk scheduling mainly tries to reduce:

• Seek time - time required to move the disk head.
• Rotational latency - time waiting for the required sector to rotate under the head.
• Total head movement - distance traveled by the disk head.
• Response time - time taken to begin servicing a request.

A disk contains cylinders numbered 0-199. Initial head position: 53. Request queue:
98, 183, 37, 122, 14, 124, 65, 67
Calculate total head movement using:

• FCFS
• SSTF
• SCAN
• C-SCAN

For SCAN and C-SCAN, we need to specify the initial direction. We'll assume the head initially moves toward cylinder 199.

FCFS

FCFS serves requests exactly in the order given. Request sequence:

53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67

Calculate each movement:

Movement	Distance
53 > 98	45
98 > 183	85
183 > 37	146
37 > 122	85
122 > 14	108
14 > 124	110
124 > 65	59
65 > 67	2

Total: 45+85+146+85+108+110+59+2 = 640
FCFS Answer: Total Head movement = 640

SSTF

Shortest Seek Time First selects the request closest to the current head position. Initial position:53
Requests: 98, 183, 37, 122, 14, 124, 65, 67

Step 1
From 53:

|53 - 98|	=	45
|53 - 183|	=	130
|53 - 37|	=	16
|53 - 122|	=	69
|53 - 14|	=	39
|53 - 124|	=	71
|53 - 65|	=	12
|53 - 67|	=	14

Closest = 65

Movement:
53->65=12
Step 2
Current = 65.
Closest request = 67
65->67=2
Step 3
Current = 67.
Closest = 37
67->37=30
Step 4
Current = 37.
Closest = 14
37->14=23
Step 5
Current = 14.
Closest remaining = 98
14->98=84
Step 6
Current = 98.
Closest = 122
98->122=24
Step 7
Current = 122.
Closest = 124
122->124=2
Step 8
Remaining request = 183
124->183=59
SSTF sequence
53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183
Total:12+2+30+23+84+24+2+59 = 236

SSTF Answer: Total head movement = 236 cylinders. 

SCAN
Assumption: Initial direction is toward 199. Requests greater than 53:


Tracks: 65, 67, 98, 122, 124, 183 
Requests less than 53:
37, 14
The head moves toward 199, servicing requests on the way.
Service sequence
53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 37 -> 14 -> 0
Why does it go to 199 and then 0?

Because SCAN behaves like an elevator: it continues to the end of the disk before reversing direction.

Calculate:
Movement
Distance
53 -> 65
12
65 -> 67
2
67 -> 98
	31
98 -> 122
	24
122 -> 124
	2
124 -> 183
	59
183 -> 199
	16
199 -> 37
	162
37 -> 14
	23
14 -> 0
	14


Total: 12+2+31+24+2+59+16+162+23+14 = 345

SCAN Anwer: 345 Cylinders

C-SCAN
C-SCAN moves in only one direction. Assume the direction is toward 199. It services:

tracks: 65, 67, 98, 122, 124, 183

Then reaches 199.

After reaching 199, it jumps to 0 and continues in the same direction.

Service sequence
53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 0 -> 14 -> 37
Calculate


Movement
Distance
53 -> 65	
12
65 -> 67
	2
67 -> 98
	31
98 -> 122
	24
122 -> 124
	2
124 -> 183
	59
183 -> 199
	16
199 -> 0
	199
0 -> 14
	14
14 -> 37
	23

Total: 12+2+31+24+2+59+16+199+14+23 = 382

C-SCAN Answer: 382 Cylinders

Important note

SCAN and C-SCAN answers depend on the assumed initial direction. If the question doesn't specify the direction, you should explicitly state your assumption.